﻿ #define_CRT_SECURE_NO_WARNINGS 1	
     leetcode
     4. 摆动序列（medium）
     5. 最⻓递增⼦序列（medium）
     6. 递增的三元⼦序列（medium）
     4. 摆动序列（medium）
     https ://leetcode.cn/problems/wiggle-subsequence/submissions/586366533/

 class Solution {
 public:
     int wiggleMaxLength(vector<int>& nums) {
         //贪心策略，统计所有峰值点个数
         //难点在于如何找到峰值点
         int ret = 0;
         int left = 0;
         int n = nums.size();
         if (n < 2)
             return n;
         for (int i = 0; i < n - 1; i++)
         {
             int right = nums[i + 1] - nums[i];
             if (right == 0)continue;//排除相同点的情况
             if (right * left <= 0)
                 ret++;
             left = right;
         }
         return ret + 1;//最后一个点统计不到
     }
 };
 5. 最⻓递增⼦序列（medium）
     https ://leetcode.cn/problems/longest-increasing-subsequence/description/

 class Solution {
 public:
     int lengthOfLIS(vector<int>& nums) {
         //贪心策略：开一个新数组
         //新数组i下标存储i+1长度的序列的最后一个元素（该元素应该为该情况下的最小值）
         //遍历原数组若小于等于新数组的某个元素直接替换，否则插入到新数组
         //二分优化
         vector<int> ret;
         int n = nums.size();
         ret.push_back(nums[0]);
         for (int i = 0; i < n; i++)
         {
             if (nums[i] > ret.back())
                 ret.push_back(nums[i]);
             else
             {
                 int left = 0, right = ret.size() - 1;
                 while (left < right)
                 {
                     int mid = left + (right - left) / 2;
                     if (ret[mid] < nums[i])
                         left = mid + 1;
                     else right = mid;
                 }
                 ret[left] = nums[i];
             }
         }
         return ret.size();
     }
 };
 6. 递增的三元⼦序列（medium）
     https ://leetcode.cn/problems/increasing-triplet-subsequence/submissions/586810651/

 class Solution {
 public:
     bool increasingTriplet(vector<int>& nums) {
         //同上一题，甚至不用做到二分优化，因为三元子序列是定长的
         int n = nums.size();
         vector<int> ret;
         int a = nums[0];
         int b = INT_MAX;
         ret.push_back(a);
         for (int i = 1; i < n; i++)
         {
             if (nums[i] > b)return true;
             else if (nums[i] > a) b = nums[i];
             else a = nums[i];
         }
         return false;
     }
 };